package DP;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/coin-change-2/
 */
public class CoinExchange {

    //计算有多少种组合的
    public int change_num(int amount, int[] coins) {
        if(amount==0){
            return 0;
        }
        int num = coins.length;
        if(num == 0){
            return 0;
        }
        //用amount + 1的空间是因为，后面的计算，直接用的对应硬币分值来存储定位的。
        int[] dp = new int[amount+1];

        dp[0] = 1;//这里1是因为，如果分值和硬币分值相当，那就是计数1
        for(int i=0; i<num; i++){//要先遍历硬币，因为按照硬币金额加上去的
            for(int j=coins[i]; j<=amount; j++){//从当前硬币开始
                //上面的 j=coins[i] 很重要，就是取到正确的
                dp[j] = dp[j] + dp[j-coins[i]];
            }
        }

        return dp[amount];
    }

    //需要的最少,还是找转换公式  某个的最少是  F[x] = min(F[x], F[x]+Coin)
    //这背后有一个取还是不取的情况
    public int change_min(int amount, int[] coins) {
        if(amount==0){
            return -1;
        }
        int num = coins.length;
        if(num == 0){
            return -1;
        }
        //用amount + 1的空间是因为，后面的计算，直接用的对应硬币分值来存储定位的。
        int[] dp = new int[amount+1];
        Arrays.fill(dp,1,dp.length,Integer.MAX_VALUE);

        for(int i=0; i<num; i++){//要先遍历硬币，因为按照硬币金额加上去的
            for(int j=coins[i]; j<=amount; j++){//从当前硬币开始
                if(dp[j-coins[i]] != Integer.MAX_VALUE){
//上面的 j=coins[i] 很重要，就是取到正确的
                    dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1);
                }
            }
        }
        for(int i=0; i<dp.length;i++){
            if(dp[i] == Integer.MAX_VALUE){
                dp[i] = -1;
            }
        }

        return dp[amount];
    }



    public static void main(String[] args){
        int[] n = new int[]{-1,1,1,1};

    }


}
